#define _CRT_SECURE_NO_WARNINGS 1 
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>


//离散存储 [链表]

//定义：
//	n个结点离散分配.
//	彼此通过指针相连.
//	每个结点只有一个前驱结点， 每个结点只有一个后继结点.
//	首结点没有前驱结点，尾结点没有后继结点.

//专业术语：
//	首结点：第一个有效结点
//	尾结点：最后一个有效结点
//	头结点：头结点的数据类型与链表中结点的类型相同
//			位于第一个有效结点之前的那个结点，并不存放有效数据
//			加头结点的目的主要是为了方便对链表的操作
//	头指针：指向头结点的指针变量
//	尾指针：指向尾结点的指针变量

//如果希望通过一个函数对链表进行处理，我们至少需要接收链表的哪些参数？
//    只需要一个参数：头指针
//    因为我们通过头指针可以推算出链表中的其他所有参数


//分类：
//	单链表：
//	双链表：每一个结点有两个指针域
//	循环链表：能通过任何一个结点找到其他所有结点
//	非循环链表：

//算法：
//	遍历
//	查找
//	清空
//	销毁
//	求长度
//	排序
//	删除结点
//	插入结点

//  !!! 算法：
//		  狭义的算法是与数据的存储方式密切相关
//		  广义的算法是与数据的存储方式无关
//		  泛型：利用某种技术达到的效果就是:不同的存储方式,执行的操作是一样的

typedef struct Node
{
	int data;//数据域
	struct Node *pNext;//指针域
}NODE,*PNODE;// NODE <==> struct Node，PNODE <==> struct Node *

//函数声明
PNODE Create_list(void);//创建链表
void Traverse_list(PNODE pHead);//遍历链表
bool Is_empty(PNODE pHead);//判空
int Length_list(PNODE pHead);//获取链表长度
bool Insert_list(PNODE, int, int);//插入结点
bool Delete_list(PNODE, int, int*);//删除结点
void Sort_list(PNODE);//排序


int main(void)
{
	int pos = 0, val = 0;

	//生成头指针
	PNODE pHead = NULL;// <==> struct Node *pHead = NULL;

	//创建链表
	pHead = Create_list();//Create_list()的功能：创建一个非循环单链表，并将该链表的头结点地址赋给pHead

	//判空
	if (Is_empty(pHead))
	{
		printf("链表为空！\n");
	}
	else
	{
		printf("链表不为空！\n");
	}

	//获取链表的长度
	int len = Length_list(pHead);
	printf("链表的长度为%d\n",len);

	//遍历链表
	printf("链表的内容为：");
	Traverse_list(pHead);

	//排序
	printf("升序排列为:>\n");
	Sort_list(pHead);
	Traverse_list(pHead);

	//插入结点
	//在pHead所指向链表的第pos个结点前面插入一个新的结点，该结点的值是val，并且pos的值是从1开始
	printf("您想在哪个位置插入结点:>");
	scanf("%d", &pos);
	printf("请输入您要插入的结点值:>");
	scanf("%d", &val);
	if (Insert_list(pHead, pos, val))
	{
		printf("插入成功！\n");
		Traverse_list(pHead);
	}
	else
	{
		printf("插入失败！\n");
	}

	//删除结点
	pos = 0;
	printf("您想删除哪个位置的结点:>");
	scanf("%d", &pos);
	if (Delete_list(pHead, pos, &val))
	{
		printf("删除成功！\n");
		Traverse_list(pHead);
	}
	else
	{
		printf("删除失败！\n");
	}


	return 0;
}

//创建链表
PNODE Create_list(void)
{
	int i = 0;
	int len = 0;//用于存放有效结点的个数
	int val = 0;//用于临时存放用户输入的结点值

	//动态内存分配了一个不存放有效数据的头结点
	PNODE pHead = (PNODE)malloc(sizeof(NODE));
	if (NULL == pHead)
	{
		printf("内存空间分配失败，程序终止！\n");
		exit(-1);
	}

	//指针变量pTail始终指向链表尾结点的地址
	PNODE pTail = pHead;
	pTail->pNext = NULL;

	printf("请输入您要生成的链表结点的个数:>");
	scanf("%d", &len);

	for (i = 0; i < len; ++i)
	{
		printf("请输入第%d的结点值:>", i + 1);
		scanf("%d", &val);

		PNODE pNew = (PNODE)malloc(sizeof(NODE));
		if (NULL == pNew)
		{
			printf("内存空间分配失败，程序终止！\n");
			exit(-1);
		}
		pNew->data = val;
		pTail->pNext = pNew;
		pNew->pNext = NULL;
		pTail = pNew;
	}
	return pHead;
}

//遍历链表
void Traverse_list(PNODE pHead)
{
	PNODE p = pHead->pNext;

	while (NULL != p)
	{
		printf("%d ", p->data);
		p = p->pNext;
	}
	printf("\n");
}

//判空
bool Is_empty(PNODE pHead)
{
	if (NULL == pHead->pNext)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//获取链表长度
int Length_list(PNODE pHead)
{
	PNODE p = pHead->pNext;
	int len = 0;

	while (NULL != p)
	{
		++len;
		p = p->pNext;
	}
	return len;
}

//插入结点(在pHead所指向链表的第pos个结点前面插入一个新的结点，该结点的值是val，并且pos的值是从1开始)
bool Insert_list(PNODE pHead, int pos, int val)
{
	int i = 0;
	PNODE p = pHead;

	while (NULL != p && i < pos - 1)
	{
		p = p->pNext;
		++i;
	}

	if (i > pos - 1 || NULL == p)
	{
		return false;
	}

	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	if (NULL == pNew)
	{
		printf("插入结点时，动态内存分配失败！\n");
		exit(-1);
	}

	pNew->data = val;
	PNODE q = p->pNext;
	p->pNext = pNew;
	pNew->pNext = q;

	return true;
}

//删除结点
bool Delete_list(PNODE pHead, int pos, int *pVal)
{
	int i = 0;
	PNODE p = pHead;

	while (NULL != p->pNext && i < pos - 1)
	{
		p = p->pNext;
		++i;
	}

	if (i > pos - 1 || NULL == p->pNext)
	{
		return false;
	}

	PNODE q = p->pNext;
	*pVal = q->data;
	//删除p结点后面的结点
	p->pNext = p->pNext->pNext;
	free(q);
	q = NULL;

	return true;
}

//排序
void Sort_list(PNODE pHead)
{
	int i = 0, j = 0, t = 0;
	int len = Length_list(pHead);
	PNODE p, q;

	for (i = 0, p = pHead->pNext; i < len - 1;++ i,p=p->pNext)  //类似于连续数组排序中的: for (i = 0; i < len - 1; ++i)
	{                                                           //                        {
		for (j = i + 1,q = p->pNext; j < len;++ j,q=q->pNext)   //                         	  for (j = i + 1; j < len; ++j)
		{                                                       //                            {
			if (p->data > q->data)                              //                                if(a[i] > a[j])
			{                                                   //                                {
				t = p->data;                                    //                                   t > a[i];
				p->data = q->data;                              //                                   a[i] > a[j];
				q->data = t;                                    //                                   a[j] = t;
			}                                                   //                                 } 
		}                                                       //                             }
	}                                                           

	return;
}